import java.util.*;

public class Solution {
    public String LeftRotateString(String str,int n) {

        // 双端队列
        /*
        if (str == null || str.length() == 0) {
            return str;
        }

        int len = str.length(); 
        n %= len;

        Deque<Character> deque = new LinkedList<>();
        for (char c : str.toCharArray()) {
            deque.add(c);
        }

        for (int i = 0; i < n; i++) {
            deque.add(deque.pollFirst());
        }

        String res = "";

        for (char c : deque) {
            res += c;
        }
    
        return res;
        */

        // 三次reverse
        if (str == null || str.length() == 0) {
            return str;
        }

        int len = str.length(); 
        n %= len;

        char[] s = str.toCharArray();
        reverse(s, 0, len - 1);
        reverse(s, 0, len - n - 1);
        reverse(s, len - n, len - 1);

        return new String(s);

    }

    // reverse
    private void reverse(char[] s, int start, int end) {
        while (start < end) {
            swap(s, start++, end--);
        }
    }

    // 交换
    private void swap(char[] s, int a, int b) {
        char temp = s[a];
        s[a] = s[b];
        s[b] = temp;
    }
}
